//你有一个凸的
// n 边形，其每个顶点都有一个整数值。给定一个整数数组
// values ，其中
// values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。 
//
// 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之
//和。 
//
// 返回 多边形进行三角剖分后可以得到的最低分 。 
//
// 
// 
//
// 示例 1： 
//
// 
//
// 
//输入：values = [1,2,3]
//输出：6
//解释：多边形已经三角化，唯一三角形的分数为 6。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：values = [3,7,4,5]
//输出：144
//解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
// 
//
// 示例 3： 
//
// 
//
// 
//输入：values = [1,3,1,4,1,5]
//输出：13
//解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
// 
//
// 
//
// 提示： 
//
// 
// n == values.length 
// 3 <= n <= 50 
// 1 <= values[i] <= 100 
// 
//
// Related Topics 数组 动态规划 👍 355 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-09-29 20:44:39
 * @description 1039.多边形三角剖分的最低得分
 */
public class MinimumScoreTriangulationOfPolygon{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumScoreTriangulationOfPolygon fun=new MinimumScoreTriangulationOfPolygon();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int minScoreTriangulation1(int[] values) {
		int n = values.length;
		// 记忆化搜索+递归  时间on3 空间on2
		int[][] memo = new int[n][n];
		for (int[] row : memo) {
			Arrays.fill(row, -1); // -1 表示没有计算过
		}
		return dfs(0, n - 1, values, memo);
	}

	private int dfs(int i, int j, int[] v, int[][] memo) {
		if (i + 1 == j) {
			return 0; // 只有两个点，无法组成三角形
		}

		if (memo[i][j] != -1) { // 之前计算过
			return memo[i][j];
		}

		int res = Integer.MAX_VALUE;
		for (int k = i + 1; k < j; k++) { // 枚举顶点 k
			//不断切割，直到只有两个的时候会返回0+0+乘积
			int subRes = dfs(i, k, v, memo) + dfs(k, j, v, memo) + v[i] * v[j] * v[k];
			res = Math.min(res, subRes);
		}

		return memo[i][j] = res; // 记忆化
	}
	//递推  区间dp
	public int minScoreTriangulation(int[] v) {
		int n = v.length;
		int[][] f = new int[n][n]; //初始dp数组
		// 因为 i<k<j，所以i倒序,j正序
		// 如果j=i+1，说明临近，所以j从i+2开始，同时j<=n-1,所以  i<=n-3,那么i从n-3开始
//		for (int i = n - 3; i >= 0; i--) {
//			for (int j = i + 2; j < n; j++) {
//				f[i][j] = Integer.MAX_VALUE;
//				for (int k = i + 1; k < j; k++) {
//					f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + v[i] * v[j] * v[k]);
//				}
//			}
//		}
		// 按照长度遍历
		for(int len = 2 ; len <= n ; len++){
			//枚举区间长度
			for(int l = 0 ; l < n ; l++){
				int r = l + len; //根据起点和长度得出终点
				if(r >= n) continue;//符合条件的终点
				f[l][r] =  Integer.MAX_VALUE;
				for(int k = l + 1 ; k < r ; k++) //枚举最优分割点
					f[l][r] = Math.min(f[l][r], f[l][k] + f[k][r] + v[l] * v[r] * v[k]); //状态转移方程
			}
		}
		return f[0][n - 1];
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
